package problem35_Search_Insert_Position;

public class MySolution {
	public int searchInsert(int[] nums, int target) {
		int left=0,right=nums.length-1;
		while(left<=right){
			int mid=left+right>>1;
			if(nums[mid]==target)
				return mid;
			else if(nums[mid]<target)
				left=mid+1;
			else
				right=mid-1;
		}
		return Math.max(left, right);
    }
	  
	  public static void main(String[] args){
		  System.out.println(new MySolution().searchInsert(new int[]{1,3,5,6}, 5));
		  System.out.println(new MySolution().searchInsert(new int[]{1,3,5,6}, 2));
		  System.out.println(new MySolution().searchInsert(new int[]{1,3,5,6}, 7));
		  System.out.println(new MySolution().searchInsert(new int[]{1,3,5,6}, 0));
	  }
}
